class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //维护一个单调递减的stack，stack内部是temperatures数组的index。
        //如果第i天的温度高于栈顶index的温度，那么大于此栈顶index温度的值出现在i - index天，否则为0
        /**
        [73,74,75,71,69,72,76,73]
        (0(73))   1(74)比他大，73弹出res[0]=1-0
        (1(74))   2(75)比他大，74弹出res[1]=2-1
        (2(75),3(71),4(69))  5(72)比他大，弹出69res[4]=5-4   弹出71res[3]=5-3 比栈顶小，放入
        (2(75),5(72))   6(76)比他大，弹出72res[5]=6-5    弹出75[2]=6-2
        (6(76),7(73)) 其他位置默认为0
         */
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}